import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class hu {
    private static final Random random=new Random();
    public static int select(List<Integer> arr,int a){
        if(arr.size()==1){
            return arr.get(0);
        }
        int pivot=arr.get(random.nextInt(arr.size()));
        List<Integer> less=new ArrayList<>();
        List<Integer> equal=new ArrayList<>();
        List<Integer> more=new ArrayList<>();
        for(int num:arr){
            if(num<pivot){
                less.add(num);
            }
            else if(num==pivot){
                equal.add(num);
            }
            else{
                more.add(num);
            }
        }
        if(a<=less.size()){
           return select(less,a);
        }
        else if(a<=less.size()+equal.size()){
            return pivot;
        }
        else{
            return select(more,a-less.size()-equal.size());
        }
    }

    public static void main(String[] args) {
        List<Integer> arr=new ArrayList<>();
        arr.add(5);
        arr.add(7);
        arr.add(78);
        arr.add(14);
        arr.add(12);
        arr.add(23);
        int a=select(arr,5);
        System.out.println(arr);
        System.out.println(a);
    }
}